/*
 * Project: Code
 * File Created at 2024/1/11
 @Type Prefect_Squares.java
 @author Goodwin
 * Website : https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked
*/

package Dynamic_Program;

public class Prefect_Squares {
    public int numSquares(int n){
        int[] dp = new int[n+1]; // dp[i] 表示 i 最少需要多少个完全平方数表示
        dp[0] = 0; // 初始化
        dp[1] = 1;
        for(int j=2;j<=n;j++){
            int min_value = Integer.MAX_VALUE;
//            想得到一种，有一个完全平方数+一个j-i*i，其中要后者组成的完全平方数最少的
            for (int i=1;i*i<j;i++) { // = ?
                min_value = Math.min(min_value, dp[j-i*i] + 1);
            }
            dp[j] = min_value ; //+1
        }
        return dp[n];
    }

}
